#include <bits/stdc++.h>
using namespace std;

// 【题目】1539. 第 k 个缺失的正整数
// 【难度】简单
// 【提交】2025.9.25 https://leetcode.cn/problems/kth-missing-positive-number/submissions/665992580
// 【标签】数组 二分查找
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] <= k)
            k++;
        }
        return k;
    }
};

/**
 * @brief 学习总结：
 *  
*/


/*
--------------------------------------------------------------------------------------------------------------
（学习笔记：LeetCode 1539「第 k 个缺失的正整数」）​​
​​（提交记录：C++，用时 0 ms，内存 9.5 MB）​​
一、题意与模型
给定一个严格升序排列的正整数数组 arr和一个整数 k，要求找到第 k个缺失的正整数。缺失的正整数是指不在数组 arr中且从 1 开始连续计数的正整数。

二、算法思路
利用数组的有序性，通过遍历数组并动态调整 k的值来间接找到第 k个缺失的正整数。核心思想是：第 k个缺失的正整数至少是 k，数组中的每个元素如果小于等于当前的 k，说明它占据了一个缺失数字的位置，需要将 k增加 1 来补偿。

三、你的实现思路
cppcpp下载复制运行class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] <= k)
                k++;
        }
        return k;
    }
};


四、逐行注释（带细节提醒）
cppcpp下载复制运行class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for(int i = 0; i < arr.size(); i++){  // 遍历有序数组
            if(arr[i] <= k)                   // 如果当前元素值小于等于k
                k++;                          // 说明该元素占据了一个缺失数字的位置，k需要+1补偿
        }
        return k;                             // 最终的k就是第k个缺失的正整数
    }
};


五、正确性证明
​初始状态​：第 k个缺失的正整数至少是 k（在没有缺失的理想情况下就是 k）
​补偿机制​：每当遇到一个数组元素 arr[i] <= k，说明这个元素占据了一个原本属于缺失数字的位置，因此需要将 k增加 1
​数学归纳​：遍历完成后，k的值恰好就是第 k个缺失的正整数，因为所有小于等于最终 k值的数组元素都已经被"补偿"过了

六、复杂度分析
​时间​：O(n)，其中 n 是数组 arr的长度。只需要遍历一次数组。
​空间​：O(1)，只使用了常数级别的额外空间，非常高效。

七、优缺点分析
​优点：​​
算法极其简洁，只有 5 行代码
时间复杂度最优，只需要线性时间
空间复杂度极佳，不需要额外数据结构
思路巧妙，通过调整 k而非直接计算缺失数

​缺点：​​
算法思路相对抽象，需要理解"补偿"机制
对于初学者可能不太直观

八、改进建议
当前算法已经是最优解，无论是时间还是空间复杂度都无法进一步优化。如果需要更易理解的版本，可以考虑使用二分查找方法，但时间复杂度相同且代码更复杂。

九、一句话总结
该算法通过巧妙的"动态补偿"机制，在遍历有序数组的过程中调整目标位置 k，以 O(n) 时间和 O(1) 空间的高效方式准确找到了第 k个缺失的正整数，体现了算法设计中"思维转变"的精妙之处。
--------------------------------------------------------------------------------------------------------------
*/